Fehr was born on in [[Tel Aviv, Israel]], the son of Gila (née Lachmann), a [[day care]] supervisor, and Uri/Ury Ernst Fehr, a [[Jerusalem]]-born geophysicist and marketing executive.<ref>{{cite book | url = https://books.google.com/books?id=c29mAAAAMAAJ&q=%22FEHR,+Uri,+US,+geophysicist%22&dq=%22FEHR,+Uri,+US,+geophysicist%22&source=bl&ots=aEVU03Eyec&sig=SLiL99pcN4LKFzDWC-uoMDztpYc&hl=en&redir_esc=y | title = Who's Who in World Jewry: A Biographical Dictionary of Outstanding Jews | first1 = Harry | last1 = Schneiderman | first2 = Itzhak J. | last2 = Carmin | publisher = Pitman Publishing Corporation | year = 1972 | page = 237}}</ref> His parents' families are [[Ashkenazi Jewish]], and they [[Aliyah|immigrated]] to Israel from Germany and the Netherlands.<ref>{{cite news| url=http://nl.newsbank.com/nl-search/we/Archives?p_product=WT&p_theme=wt&p_action=search&p_maxdocs=200&p_topdoc=1&p_text_direct-0=0EF9AF9D590B3C5A&p_field_direct-0=document_id&p_perpage=10&p_sort=YMD_date:D&s_trackval=GooglePM | title=He owes it all to `Mummy' | first = Eirik | last = Knutzen | date = 5 November 2001 | work = The Washington Times | page = B5}}</ref><ref name="Jweekly">{{cite news | url = https://www.jweekly.com/2005/11/25/israeli-actor-plays-muslim-terrorist-in-showtime-s-sleeper-cell/ | title = Israeli actor plays Muslim terrorist in Showtime’s ‘Sleeper Cell’ | location = Los Angeles | date = 25 November 2005 | work = The Jewish News of Northern California | access-date = 19 August 2017}}</ref> He trained at the [[Bristol Old Vic Theatre School]] in [[England]] after taking a very brief drama class in [[Frankfurt]], [[Germany]]. He served in the [[Israeli Navy]] from 1989 to 1992<ref>{{cite web | url = http://www.somethingjewish.co.uk/articles/69_interview_with_oded_.htm | title = Interview with Oded Fehr | work = Somethingjewish.co.uk | date = 1 December 2001 | publisher = JMT Ventures | access-date = 19 August 2017}}</ref> and used to work security for the Israeli airline [[El Al]]<!-- in [[Germany]]-->.<ref name="Jweekly" />
