You have to ask for a task from a noble, then he may decide to give that. There may be certain requirements before this quest/job is unlocked, but I'm pretty sure you can be quite low on renown (below 100) and on disposition (maybe even zero) to the nation of the quest giver. Also, accepting the contract will lower all other factions disposition, to 0 (if they are not currently engaged in conflict with the hiring nation) or to -40 (if they are engaged), as in Warband.