Yes they do indeed. Find out how to put your headset into "discoverable mode", either by reading the manual or googling your headset's model number, and then go to Settings>General>Bluetooth in your iPhone and flip the switch to "on". Then, it'll show your headset and you've just got to select it under "devices". Easy as pie