Soulmate is a 2007 song by the English singer and songwriter Natasha Bedingfield . `` Soulmate '' is a pop song written and produced by Natasha Bedingfield , Mads Hauge and David Tench for Bedingfield 's second album , N.B. ( 2007 ) .