The 'palestinians' rejected UN Resolution 181 in 1947 and attacked the Jewish community right away.  Israel declared independence six months later and was recognized by many countries.  Israel didn't need a fake 'palestine' then and doesn't need it now for its 'legitimacy'.  That contention is just plain anti-Semitic.
Is there any other country in the world that you consider illegitimate?  No?  Then you meet the US, UK, and EU definition of an anti-Semite.  Congratulations!