In a hydrocarbon synthesis process, nitrogen is cryogenically removed from natural gas to produce a synthesis gas feed comprising methane which is substantially free of nitrogen. This feed is converted to a synthesis gas comprising a mixture of H.sub.2 and CO which is substantially free of the HCN and NH.sub.3 hydrocarbon synthesis catalyst deactivating nitrogen species. This reduces the need for rejuvenating the hydrocarbon synthesis catalyst. During the cryogenic separation, C.sub.2+ hydrocarbons are separated from the natural gas and all or a portion of the separated C.sub.2 -C.sub.4 hydrocarbons are added to the methane feed before it is converted into syngas, to increase syngas production. All or a portion of the separated C.sub.2 -C.sub.3 hydrocarbons may be removed as LPG.