Upon their arrival in Lagos in August 1973, Wings found the circumstances far from perfect. They rented houses near the airport in Ikeja, an hour's journey from EMI's studio in Apapa. While Paul McCartney considered using some local musicians during the sessions, the reception from some of the locals increased his resolve to go it alone.

We went there intending to use some of the local musicians. We thought we might have some African brass and drums and things. We started off thinking of doing a track with an African feel, or maybe a few tracks, or maybe even the whole album, using the local conga players and African fellows. But when we got there, and we were looking round and watching the local bands, one of the fellows, Fela Ransome-Kuti, came up to us after a day or two, and said: 'You're trying to steal the black musicians' music.' We said, 'No, we're not! Do us a favour, Fela. We do all right as it is, actually. We sell a record here and there. We just want to use some of your guys.' But he got heavy about it, until in the end we thought, 'Blow you then, we'll do it all ourselves.' So we did and the only guy from Africa we used, Remi Kebaka, was someone we met in London, then we discovered that he came from Lagos. But that was purely coincidental.
Paul McCartney

Wings met Ransome-Kuti through former Cream drummer Ginger Baker, who owned ARC Studios in Ikeja. Baker was keen for Wings to record the whole album at ARC, but only one Band On The Run session took place there, for the song Picasso's Last Words (Drink To Me).

Around two weeks into their Nigerian visit, Paul and Linda McCartney were mugged at knifepoint, and demo tapes of the songs were stolen. Paul had to remember the words and music for the songs.

After we had been in Lagos a couple of weeks, we were held up and robbed at knife point. Linda and I had set off like a couple of tourists, loaded with tapes and cameras, to walk to Denny's house, which was about twenty minutes down the road. A car pulls up beside us and goes a little bit ahead. Then a guy gets out and I thought that he wanted to give us a lift. So I said, 'Listen, mate, it's very nice of you, thanks very much but we are going for a walk.' I patted him on the back and he got back in the car, which went a little way up the road. It stopped again and Linda was getting a bit worried. Then one of them, there were about five or six black guys, rolled down the window and asked, 'Are you a traveller?' I still think that if I had thought really quickly and said, 'Yes, God's traveller,' or something like that to freak them out a bit, maybe they would have left us alone. But I said, 'No, we are just out for a little walk. It's a holiday and we are tourists,' giving the whole game away. So, with that, all the doors of the car flew open and they all came out and one of them had a knife. Their eyes were wild and Linda was screaming, 'He's a musician, don't kill him,' you know, all the unreasonable stuff you shout in situations like that. So I'm saying, 'What do you want? Money?' And they said, 'Yeah, money,' and I handed some over. Shaking, we walked on home and we were just sitting down having a cup of coffee to try and recover our nerves and there was a power cut. We thought they had come back and cut the power cables. We had a lot of trouble sleeping that night and got back to the studio the next day to be told, 'You're lucky to be alive. If you had been black, they'd have killed you. But, as you're white, they know you won't recognise them.' I wanted to call the police, but everyone said it would do no good there at all. With that we had to carry on and make the record, adding to the pressure, which we had already got.
Paul McCartney

Shortly afterwards, McCartney collapsed outside the studio after complaining of chest pains.

It seemed stuffy in the studio, so I went outside for a breath of fresh air. If anything, the air was more foul outside than in. It was then that I began to feel really terrible and had a pain across the right side of my chest and I collapsed. I could not breathe and so I collapsed and fainted. Linda thought I had died.

The doctor seemed to treat it pretty lightly and said it could be bronchial because I had been smoking too much. But this was me in hell. I stayed in bed for a few days, thinking I was dying. It was one of the most frightening periods in my life. The climate, the tensions of making a record, which had just got to succeed, and being in this totally uncivilised part of the world finally got to me.

Paul McCartney

In the studio

As with The Beatles' Magical Mystery Tour and Abbey Road, some of McCartney's best solo and Wings work emerged from the toughest circumstances.

EMI's studio in Lagos was a far cry from the state-of-the-art conditions at Abbey Road. The studio was situated next onto a noisy pressing plant, and construction was not complete. The mixing desk was faulty, there were no backup facilities, no acoustic baffle screens, and the only microphones were a set found in a cardboard box inside a cupboard.

Furthermore, the tropical storms meant led to frequent power cuts. Geoff Emerick, manning the eight-track Studer recording console, was in charge of making a success of the performances. Eventually they recorded seven of the nine tracks on Band On The Run.

Recording continued in England following Wings' return on 23 September. Two weeks later they entered George Martin's AIR Studios in London, where most the tapes were first copied to 16-track to prepare for overdubbing.

Extra vocals, percussion and orchestration – the latter by Tony Visconti – were added at AIR. Band On The Run was completed in early November 1973 with three days of mixing in Kingsway Studios.

In addition to the nine songs on Band On The Run, the sessions also yielded seven other recordings, : Helen Wheels, which was issued as a standalone single; Zoo Gang, which became the theme to a British television show and was later the b-side of the Band On The Run single; B-side To Seaside, used as a b-side to the Suzy And The Red Stripes single Seaside Woman, and was later re-recorded; and Oriental Nightfish, which was later used in a cartoon soundtrack, and again was re-recorded at a later date.