Kilroy was here
This was a graffito, of unknown origin but used predominantly by members of the US and UK military and predominantly during WWII. It was often combined with an earlier cartoon image, known as Chad, although the two aren't related apart from that conjunction.
In order to trace the origin of 'Kilroy was here', we will need to disentangle it from the Chad image and the 'Wot, no ...' or 'What no...', text that also often accompanied the cartoon. This text was usually a jocular a complaint against a shortage of some commodity of other.
The two text graffiti. that is, 'Kilroy was here' and 'Wot, no...' both predate Chad and are often found separately from it.
An example of the use of 'Wot, no...' is found in the USA in 1932, in the newspaper The Day, December 1932, in an advert for a jewellery store. The knowing use of the phrase as an attention grabber suggests that the phrase was in the public's mind at that time and I would expect pre-1932 examples to turn up in time.
A nice comic example of the use of the expression comes in a story from England in 1945, which was reprinted in the Virginia newspaper The Bee, on Christmas Eve that year:
MANCHESTER, England - Men at a military camp near here scribbled over the walls of the canteen: "Wot! No beer!" "Wot! No fags!" "Wot! No eggs". The commanding officer threatened 28 days detention to anyone caught, but when he returned to his office after parade, he found on his blotting pad: "Wot; Only 28 days!"
The Chad image is sometimes credited to the British cartoonist George Edward Chatterton (a.k.a. Chat), but that is no more certain than the origin of 'Kilroy was here' itself. The Times, in April 1946, pitched it about right when they said:
"Mr. Chad probably went through a number of evolutions at the hands of a vast number of people before reaching the present state and can claim no one man as creator. 'Wot! No father,' it might well complain."
The Kilroy was here graffito was extremely common during the latter part of WWII and into the 1950s and amounted to something of a craze - with it turning up in obscure locations all around the world.
The first reference to an example of 'Kilroy was here' that I can find is from a US History Channel video, Fort Knox: Secrets Revealed, which was broadcast in 2007. The show included a shot of a chalked graffito dated 13th May 1937. You might think that that is fairly flimsy evidence, after all, anyone can chalk and photograph a graffito. The support for the authenticity of the date comes from the context of the video. Fort Knox's gold bullion vault was loaded in 1937 and was stacked with gold bars from floor to ceiling, making the walls inaccessible. The bars weren't removed until the 1970s, when an audit was carried out. The removal of the bars for audit was filmed, and that's when the above graffito was uncovered. Unless Kilroy employed a trained snake with a piece of chalk, he must have been there on 13th May 1937.
The evidence for the existence of the phrase in 1937 seems strong, but the origin isn't known. There are many suggested derivations, notably the frequent association of the phrase with an American serviceman - Francis J. Kilroy, Jr. Two articles that purport to explain the origin, again from US newspapers, are worth reproducing here - even if they post-date the use of the phrase itself and so can't be accurate in their attribution. The first if from the New England paper The Lowell Sun, November 1945 - headed How Kilroy Got There:
The [US] Army public relations office said that a friend of Sergt. Francis J. Kilroy, Jr., of Everett, early in the war wrote on a barracks bulletin board at Boca Raton Army air field in Florida: "Kilroy will be here next week." Kilroy was ill with flu at the time. Later the catchy phrase was picked up by other airmen who changed it to: "Kilroy was here," and scribbled it on air force station walls. Kilroy himself only wrote it a couple of times. By the time Kilroy got overseas, the public relations office said, the thing had gotten out of hand and Kilroy even acquired a cousin. One sign at an Italian base said: "Kilroy's cousin, Corduroy, was here."
A few weeks later, in December 1945, The Nevada State Journal includes Kilroy's own claim to be the original Kilroy who was there:
Now awaiting a discharge at Devis-Monthan field, Tuscon, Ariz., Kilroy informed his parents here that while he was hospitalised earlier in the war a friend scrawled on the bulletin board at a Florida airbase: "Kilroy will be here next week."
Whoever the first Kilroy who 'was there' was, it wasn't Francis J., and we will probably never know.