A Woman A Man Walked By comes thirteen years after the album Polly Jean Harvey claims she is most proud of, her previous collaboration with musician and producer John Parish, Dance Hall at Louse Point.

Often overlooked by PJ fans as a side project of lesser importance than her solo albums, Harvey describes Dance Hall as an enormous turning point in her musical career. With John Parish taking over the composing duties, Polly was able to focus solely on the lyrics- an experience she found both liberating and challenging. As she told NME "I know John can write demanding and intellectual music, much more than mine, which is very simple. So it was really just to test my lyric writing."

The pair return to the Parish- music, Harvey- lyrics arrangement on A Woman A Man Walked By. The album was recorded in Bristol and Dorset in the UK and mixed by Flood.