The song, that was titled 'Man-O-War' in 1995, was written around the time of The Bends, but never made it on to that album. The next attempt at recording a definitive version took place in early september 1995 during the same sessions that also produced 'Lucky' and three Street Spirit b-sides.

Radiohead are to release a new single Street Spirit (Fade Out) on January 22. It will be backed by three new songs, including 'Bishop's Robes'. Other new B-sides under consideration are 'Man of War' and 'Subterranean Homesick Alien (Uptight)'.

Thom Yorke told NME: "'Man of War' is very melodramatic. Too melodramatic. When we started out, it was just a homage to Bond themes really. I like it. It's pretty much the opposite to everything we're writing."

The earliest known performance, probably the live premiere, comes from the show on october 2nd 1995 at the Mercury Lounge in New York City:

The song was part of most sets in november 1995, but only a few recordings are available. Often Thom would vary the lyrics in the "worms will come for you" section. The other lyrics were unchanged compared to the Mercury Lounge version from october 2nd and are therefore not included in this overview:

The live performance from november 20th 1995 in Montpellier was released in 2017 on the cassette that was part of the OKNOTOK 20th anniversary release of OK Computer:

'Man of War' was attempted early in the OK Computer sessions, but again the band failed to record a satisfying version. This take, from the april 1996 demo sessions at Chipping Norton Studios, received overdubs (strings and perhaps also some vocal parts) during the sessions for A Moon Shaped Pool, probably in connection with the band's work on the "other Bond song" 'Spectre'. This version was released on the OKNOTOK 20th anniversary edition of OK Computer.

The "OK OUTTAKES" leak contains a take of the song with no strings, and a take with the full string track:

This page, titled 'stuck in a frozen lake', appeared on radiohead.com during the recording of OK Computer and features a text by Thom with notes about songs that were around then.
The relevant section was not highlighted in red letters in the original page:

an airbag saved my life* in an interstella burst i am back to save the universe computer drums bass wrong lift* is hard work you been stuck in a lift we been trying to reach you thom the belly of the whale (thanks Rei xxxx) paranoid android* get busy with the shakers while im fast asleep could you stop the noise im trying ta get some rest this the place it wont hurt ever again karma police* girl with hitler hairdo everybodys friend life in a glasshouse phew for a minute there i lost myself i lost myself sit down your safe now polyethelene*will never break down swirly self announcements. stuck in a frozen lake. the penultimate place in dante's hell. last flowers till the hospital*is a sign discovered in oxford -my unhealthy obsession with these institutions. analysts may get the connection. ambulances scream past my house at all hours of the day and night like the confessionals of Larkin's "Ambulan s." let down*in the midst of monster tour the momentum getting drunk to talk bombarded by dangerously high levels of radiation from xray machines. one day, one day... climbing up the walls*both managers and record company are nervous about such a nasty sound coming out of the speakers. this is a good sign. dogwander* bring on another take better than another cake. nude* it is a mans world. and this one is very confused and will have sex with anything woman who comes within a mile radius. but feels bad about it. so doesnt. exit song (for a film)* cannot be listened to more than once in a row. which made recording it easy. or not. but what film? big boots* it was a long time ago and i cant remember. a whole orchestra watching the film and playing along. real life is dull. i am i the white lotus flying off the quay with barbara bach.
(information incomplete)
....>>>>i like the idea of you listening to our recordings with your head resting gently in emptiness. or before going out. or when you've come back. i dont like the scientists breaking down its molecular structure and teaching it in O level chemistry i ont want to have expain it but it worries me stupid. there is a lot of crying goes into making things.<<<<.... the masters tell us that there is an aspect of our minds that is its fundamental basis, a state called "the ground of the ordinary mind." It functions like a storehouse, in which the imprints of past actions caused by our negative emotions are all store like seeds. when the right conditions arise, they germinate and manifest as circumstances and situations in our lives. if we have a habit of thinking in a particular pattern, positive or negative, then these tendencies will be triggered and provoked very easily and recurr and go on recurring. With constant repetition our inclinations and habits become steadily more entr ched and continue, increasing and gathering power even when we sleep. This is how they come to determine our life, our death our rebirth.

This still image from the Bond movie The Spy Who Loved Me shows the scene Thom refers to in the comment above:

The fourth and - as far as known - final attempt at recording the song took place on march 12th 1998 for the soundtrack to the film 'The Avengers', but again they just couldn't get it to sound right. A sequence comprised of several bits from that day appeared in Meeting People Is Easy:

Thom: "We ditched it because we were so messed up and we went in, tried to do the track, but we just couldn't do it. It was actually a really difficult period of time. We had a five week break and all the shit was coming to the surface. It was all a bit weird - I mean we went in and tried to do this old track that we had and it just wasn't happening at all. It was a real low point after it. It was quite an early song, written around the time of The Bends and it didn't make it on to The Bends. We couldn't find the proper way into it or whatever."

The rear artwork of Meeting People Is Easy also featured the lyrics to the song (here taken from the DVD edition):

The song made its only live appearance since 1995 in a concert in Salamanca, Spain on august 7th 2002, when Radiohead played some songs requested by the audience:

2002 Iberian tour

july 2002

august 2002

	Up On the Ladder [7]	22			26	27		31	01		05		07
	Lift [4]	22			26			31				06
	Man of War [1]												07