The phrase out of the blue means without warning, completely unexpectedly.
It is from a bolt out of, also from, the blue, denoting a sudden and unexpected event, a complete surprise, with reference to the unlikelihood of a thunderbolt coming from a clear blue sky. For example, The Standard (London) of 26th August 1863 had:
Murder now rises up before us, gaunt and unmitigated, in a circle where all seemed lovely, virtuous, and peaceful. This is verily “a bolt out of the blue”—the lightning flash in a sunny sky.
The Dundee Courier & Argus (Dundee, Scotland) of 28th April 1875 thus began its account of an incident at the House of Commons:
London, Tuesday Evening.
A bolt out of the blue struck this afternoon. Nothing calmer than the Parliamentary sky could be imagined. The House of Commons was scantily filled. Questions had been as dull and heavy as a West Indian summer day. In the lobbies members were complaining that nothing was moving.
The earliest known use of out of the blue is from The Spectator (London) of 22nd February 1879, at the beginning of an article titled The “Times” on the standing Army of India:
What is the Times at? Twice this week, the organ of her Majesty’s Government has fired off articles so completely “out of the blue” that it is difficult to believe they are uninspired, which point [sic] to some impending coup d’état or coup de théâtre to be immediately struck in India.
The phrase out of the blue has the same meaning as out of a clear (blue) sky and variants. The earliest instance that I have found is from The Republican Compiler (Gettysburg, Pennsylvania) of 28th June 1836:
The late veto of President Jackson on the bill to fix a day for the yearly adjournment of Congress, was like a clap of thunder out of a clear sky. It took both the friends and enemies of the administration by surprise.
The Gloucester Journal (Gloucester, Gloucestershire) of 22nd June 1878 had:
The Conservative party is famous for its stolid cohesion; but although reunion will presently be accomplished, the usually compact column has been riven this week as though by a thunderbolt shot suddenly out of a blue sky.
On 29th June 1894, The Brown County World (Hiawatha, Kansas) published an article which thus begins:
Like a flash of lightning and a crash of thunder, out of a clear, blue sky, so came the report throughout Walnut township Wednesday morning, June 13, that Mr. Andrew Carothers is no more among the living on earth.
An early use of out of a blue sky without explicit reference to thunder is from the Bedfordshire Advertiser and Luton Times (Luton, Bedfordshire) on 23rd April 1909, which criticised the “diatribe” that Winston Churchill “directed against his colleagues in the Cabinet” about the Navy (at that time, Winston Churchill (1874-1965) was President of the Board of Trade and MP for the constituency of Dundee):
He [= Churchill] has apparently forgotten his utterances at Dundee in October last, when he spoke of the way in which crises and difficult situations can suddenly arise; how they come out of a blue sky with scarcely any warning or premonitory sign, and how very vain it would be for a nation like ourselves to trust merely to the stipulations of international agreements, or to the smooth phrases of ceremonious diplomacy.
word histories 