Early instances of 'frank and fearless'
The earliest match for "frank and fearless" that a Google Books search turns up is from 1793 and refers to native African people of the Gold Coast region. From Bryan Edwards & Arthur Broughton, The History, Civil and Commercial, of the British Colonies in the West Indies (1793):
The depression of spirits which these people [enslaved 'Eboes'] seem to be under, on their first arrival in the West Indies, gives them an air of softness and submission, which forms a striking contrast to the frank and fearless temper of the Koromantyn Negroes. Nevertheless the Eboes are in fact more truly savage than any nation of the Gold Coast; inasmuch as many tribes among them, especially the Moco tribe, have been, without doubt, accustomed to the shocking practice of feeding on human flesh.
And the next-earliest match is from "Thessalonika: A Roman Story," in The Monthly Magazine, and American Review (May 1799):
Whatever evil was meditated by the soldiers, it was impossible to avert or elude it. The towers and gates were in their hands. Circumspection or disguise, would avail nothing. If the danger had assumed any known form, suitable precautions could scarcely be discovered; but now, when all was uncertain and inscrutable, a frank and fearless deportment was most proper.
One culturally influential early user is Walter Scott, in Rokeby (1813):
And then, of humor kind and free,/ And bearing him to each degree/ With frank and fearless courtesy,/ There never youth was form'd to steal/ Upon the heart like brave O'Neale.
And from Thomas Campbell, An Essay on English Poetry (1819):
The result of activity and curiosity in the public mind [in Elizabethan England] was to complete the revival of classical literature, to increase the importance of foreign books, and to multiply translations, from which poetry supplied herself with abundant subjects and materials, and in the use of which she shewed a frank and fearless energy, that criticism and satire had not yet acquired power to overawe.
Use of 'frank and fearless' in political settings
In the political realm, an early instance appears in Niles' Weekly Register, a periodical published in Baltimore, Maryland. From a miscellaneous item in Niles' Weekly Register (February 19, 1825):
Mr. [Henry] CLAY. From the Richmond Enquirer, addressed to the editors—You will oblige one of your subscribers by inserting, in your paper, the inclosed paragraph of a letter from Mr. Clay. He states, in terms so strong, so frank and fearless, the grounds on which he will vote for Mr. Adams, in the face of instructions from a dominant party in Kentucky, a party who have prophaned the temple of their liberty, by pulling down their constitution; that it is impossible the sincerity of his motives can be doubted.
In a speech of March 7, 1828 by Congressman Richard Wilde of Georgia on a tariff bill, in Debates in Congress (1828):
In entertaining the sentiments he expresses, my colleague has, I think, adopted a theory which runs counter to his practice. No one, I am sure, feels his responsibility more sensibly, yet, no one, I am equally certain, will, when occasion requires, discharge the most painful duty, with more frank and fearless rectitude.
And from "Herkimer Convention," in the [Vincennes, Indiana] Western Sun & General Advertiser (October 23, 1830):
The president elect [Andrew Jackson] entered upon the duties of his office, and his first message developed the character and firmness of the man, as they had before appeared to the nation and the world, and gave the fullest assurances to republicans that his administration would be distinctly characterised by a speedy return and a strict adherence, to the principles of the illustrious Jefferson. In no respect have these assurances, as yet been violated, and we hazard nothing in saying, that hitherto the most sanguine expectations of the friends of the President, have been more than realized, and that his frank and fearless discharge of all the responsible duties of his high station, has commanded the admiration of all, and the approbation of many of his former opponents.
"Frank and fearless" appears in a political context in Great Britain and Australia in the same general period. From "University Commission," in the Midlothian [Scotland] Scotsman (August 19, 1826) [combined snippets from a fee-gated site]:
In such circumstances, it would be idle to expect a frank and fearless report. Our objections to the persons who compose the board are as strong as to its constitution.
From "Election for the North Riding," in the [London] Morning Post (*December 29, 1832) [combined snippets]:
I do not know to what those Gentlemen who are amusing themselves by interrupting me suppose I owe my return ; but if I do not owe it to the independent freeholders, I am at a loss to imagine to what it is owing. But this I know, that I do not owe it to any system of calumny ; I do not owe it to any system of misrepresentation; I do not owe it to any abuse of the other party ; I do not owe it to the packing of this Castle-yard with an organized band of hired men, who, of the party called Liberals, carried their liberality so far that they would allow no one to speak but themselves. — (Loud cheers.) — I do not owe the support 1 have received to such practices as these; but I do owe it, and I repeat it, to the frank and fearless declaration of my sentiments. — (Hear, hear.) — Having stated those sentiments fully and freely to the freeholders, I left my cause in their hands, I bowed to their decision ; and that decision has placed me at the top of the poll. — (Loud cheers.)
One fairly early instance appears to involve a situation in which a person in a subordinate position has faced a choice between conscience and material self-interest and embraced the former. From "Tyranny of Dr. Pye Smith," in the Staffordshire [England] Gazette and Country Standard (February 20, 1839) [combined snippets]:
This renowned Dissenting dignitary [Dr. Pye Smith] is manifestly a persecutor for conscience sake. He talks of conscientious dissent as if he could not tolerate an opinion differing from his own in regard to the best mode of upholding it; and by visiting Mr. Hanson's conscientiousness with the worst vengeance he could take upon it, he has shown his vile and rancorous intolerance in a form somewhat milder than that of the bloody Benner, only because he destitute of the bishop’s power. But it seems it is not much Mr. Hanson’s Conservative and anti-Poor Law opinions that have subjected him to Dr. Pye Smith's mean and cruel mulctures, as his manner of conducting himself with respect to those questions. Why, how should conscientious man conduct himself, good Doctor, except by a frank and fearless avowal of what he honestly believes to be for the good of his country! Does not Dr. Pye Smith mean, that when individual's convictions compel him to do all he can to avert what he conceives to be public calamities, he, finding himself unhappily opposed to a vindictive Doctor on whom he depends for some 15/ a-year, ought therefore to restrain the expression of his convictions, and thus sacrifice his integrity to his interests? Mr. Hanson spoke out his opinion like a free-born Englishman, and did nothing more.
A somewhat similar situation arises in an article in the Wexford [Ireland] Conservative (July 14, 1841) [combined snippets]:
Were we (Leinster Express) writing until dooms-day, employing angel’s pens, and pencils dipped in in heavens dews, any thing more graphic, pointed, appropriate than the following, would despair to produce It comes from our old neighbour, General Sir E. W. Trench, whose opinions are not less entitled to respect, than his principles are worthy of admiration, frank and fearless he tells the Ministry his mind, with the openness incidental to his profession ; and he places his views [in] such a simple and cogent form, that the intellect must be obtuse indeed that [is] not convinced by his reasoning, and swayed his eloquence.
In the National Library of Australia's Trove database, instances of "frank and fearless" begin in 1829 and quickly become political. From "Hobart Town," in the Sydney Gazette And New South Wales Advertiser (November 10, 1829):
In our capacity of Editor, we know Mr. M'Leay only as a private gentleman ; as Colonial Secretary, we know him not. We seek information from every quarter to which we can gain access, public or private, official or non-official; but we can honestly declare, that with Mr. M'Leay, as a Government Officer, the Editor of this paper has no manner of connexion; and that with Mr. M'Leay, in any capacity whatever, it is rare indeed that he has any communication.
We owe this as much to the character of Mr. M'Leay, and the Government of which he is so prominent a member, as to our own manhood and independence : and whoever, after this frank and fearless avowal, shall dare to repeat the silly slanders of the Tasmanian, must take upon himself the responsibility of a retailer of known and wilful falsehoods.
And perhaps more closely on point, from a letter to the editor of the [Adelaide] South Australian Register (August 9, 1853):
It has been my object ever to be thoroughly independent, and to have the free and unfettered expression of my own thoughts; in doing so I have always been frank and fearless with those whose rank and office made them my superiors ; and as I ever have, so will I now maintain my just right to give them unchecked utterance to my fellows. In the present controversy I trust I have never forgotten what is due to others, nor to my own self-respect; and I retire with the consciousness that I have done some service to my adopted country, and to the effort at constructing for her a good and wise system of government.
'Frank and fearless' advisors in the Westminster tradition
The earliest Google Books match for "frank and fearless" in connection with "Westminster tradition" is from Queensland Legislative Assembly, Parliamentary Papers, volume 6 (1991):
Simply stated, Westminster tradition holds that the public service is an anonymous, expert, politically neutral giver of frank and fearless advice and implements the policies of the Minister and Cabinet. Public servants are responsible to Ministers for their actions. In turn, Ministers are responsible to Parliament for the actions of their departments.
A fairly lengthy discussion of the "Westminster system" appears in Tony Ayers, "Aiming for Excellence from a Middle Ground," in the Canberra [ACT] Times (November 30, 1995):
Dr Mike Keating emphasised to the Senate Committee Conference in 1994 that the responsibility of senior public servants is to ensure that ministers are properly informed. "Having achieved that — and that does include, most importantly, frank and fearless advice and so on — as former chairman of the Public Service Board Bill Cole said, we should not continue to press the point, after they have been properly informed, to the point of nagging," he said.
Quite frankly, I have to admit to being a congenital nagger. I heard a retired senior British civil servant say that for a department head to tell a minister he or she is wrong once is essential, twice is desirable and three times is suicidal.
Having agreed with Mike Keating on the importance of giving frank and fearless advice, I believe in many respects that the real mark of a good professional public servant is how well he or she implements a policy with which he or she disagrees.
When Sir Ninian Stephen was Governor-General, he hosted a series of dinners for politicians, members of the judiciary and senior public servants. During dinner, one of the Coalition members told me he could not understand how public servants of the calibre of Geoffrey Yeend and Michael Codd, who had served the Fraser Government so admirably, could possibly serve those dreadful socialists. My reaction was to point out that he obviously did not understand the fundamental principles of the Westminster system.
It is important that we not be over-defensive. No-one denies the obligation imposed on the senior public servant to give frank and fearless advice. Nevertheless, the fundamental issue is that governments are elected by the democratic process — public servants are not.
The earliest book and newspaper database search results for "frank and fearless" are from the period 1793–1819. These instances do not use the phrase in connection with a principled approach to government service. Rather they involve a guilelessly honest and natural attitude toward human interaction—one typical of noble savages or virtuous innocents.
"Frank and fearless" as applied to the high-minded attitude of a selfless public servant came somewhat later. But instances of it exist in the United States (by 1825), in Great Britain (by 1826), and Australia (by 1856). The explicit association of "frank and fearless" with the "Westminster tradition" or the "Westminster system" are far more recent. The earliest instance I could find dates only to 1991. Nevertheless, the connection, when made, tends to apply the concept retrospectively quite far back in time.
Today, the phrase seems far more common (and meaningful) in Australia and New Zealand than elsewhere. Recent instances are rare in the UK and almost nonexistent in the United States, where a popular corresponding ideal for the newspaper business is phrased as "without fear or favor."
As for why "frank and fearless" caught on in the first place, I suspect that simple consonance played as large a role as anything else—as seems also to be the case with such set phrases as "fast and furious" and "wild and woolly" and "bright-eyed and bushy-tailed."