As AmeliaBR and Edwin Ashworth observe, the phrase "not least" is a simple exercise in understatement. For many years it has often appeared as part of the expression "last but not least," which enables a speaker to emphasize that a list in which someone or something comes last is not arranged in descending order of value or importance. Thus, for example, King Lear (in the 1608 quarto edition of the play) completes his gift of territory to Regan and then addresses Cordelia:
Lear. To thee [Regan] and thine hereditarie euer/Remaine this ample third of our faire kingdome/No lesse in space, validity, and pleasure/Then that confirm'd on Gonerill, but now our joy,/Although the last, not least in our deere loue,/What can you say to win a third, more opulent/Then your sisters.
The earliest matches in a Google Books search for "not least" for the years 1500 through 1700 are from correspondence between William Drury and William Cecil in 1567. Drury to Cecil (May 2, 1567):
The Hamiltons are furtherers of the divorce and not least gladded with the proceedings in court, hoping the rather to attain the sooner to their desired purposes.
And again Drury to Cecil (June 20, 1567):
The Lords have obtained their desire for having the castle of Edinburgh. Gathers by John Read, a Seotchman who has not least credit with the Earl of Morton, that the Lords mind to remain in Edinburgh, and not attempt any other enterprise until they hear how this that they have already done be liked of the Queen, at whose devotion they desire to be.
But the next-earliest match introduces the last/not least connection. From Richard Edwards, "Most happy is that state alone, Where words and deedes agree in one," in The Paradyse of Daynty Deuises (1578):
And last of all, which is not least of all:/For such offence, thy conscience suffer shall./As barren groundes, bringes forth but rotten weedes:/From barren words, so fruitlesse chaffe proceedes.
The first word-for-word match for "last but not least" in a Google Books search is from Nathaniel Ward, The Simple Cobler of Aggawamm in America, fourth edition (1647):
My last, but not least feare, is, That God will hardly replant his Gospel in any part of Christendome, in so faire an Edition as is expected, till the whole field hath been so ploughed and harrowed, that the soile be throughly cleansed and fitted for new feed: Or whether he will not transplant it into some other Regions, I know not: This feare I have feared these 20 years, but upon what grounds I had rather bury than broach.