2014年，在
亚足联挑战杯决赛中，
巴勒斯坦1-0战胜
菲律宾夺冠，并首次闯入亚洲杯决赛圈，但球队在亚洲杯上未能小组出线。此后巴勒斯坦队还参加了2019年的亚洲杯，但再次止步小组赛。2023年，巴勒斯坦队连续第三次晋级亚洲杯正赛。2024年1月23日，球队3-0战胜中国
香港足球代表队，取得队史亚洲杯首胜。
2023年12月，
国际足联世界杯更新了男足年终排名，巴勒斯坦国家男子足球队世界排名第99名，亚洲排名第17名。
巴勒斯坦第一支足球队于1908年在
耶路撒冷的幼儿园学校成立。在1928年，巴勒斯坦足球协会正式成立，在
巴勒斯坦足球协会成立后，一支被称为"英属巴勒斯坦托管地代表队"的球队也建立了起来。
1929年，
巴勒斯坦足球协会正式加入
国际足联。1934年，巴勒斯坦足球队参加了在
意大利举行的
国际足联世界杯预选赛，
巴勒斯坦不敌
埃及，未晋级决赛。1938年，巴勒斯坦足球队参加了世界杯预选赛。1948年，由于
巴以冲突，巴勒斯坦足球运动员分散在许多邻近
阿拉伯国家。但巴勒斯坦足球很快恢复，参加了1953年在亚历山大举行的第一届阿拉伯锦标赛。
20世纪60年代，
加沙地带足球随着正式联赛和杯赛的正规化而取得进步，巴勒斯坦球队参加了
约旦足球超级联赛。1967年-1973年，由于
巴勒斯坦领土被占领而导致巴勒斯坦足球停止。1994年，随着
巴勒斯坦民族权力机构回归祖国，巴勒斯坦足球进入了一个新时代，重组并选举了
巴勒斯坦足球协会。
2001年，
巴勒斯坦重返
国际足联世界杯预选赛，巴勒斯坦队虽在小组中排名第二，但并未出线。2002年12月，巴勒斯坦国家队参加了在
科威特举行的
阿拉伯杯足球锦标赛，获得第三名。
2007年印马泰越亚洲杯外围赛，巴勒斯坦最后一场赛事为客场对战新加坡，因被
以色列阻挠队员出境而弃权。2006年，
孟加拉国举办了第一届
亚足联挑战杯的比赛，巴勒斯坦11-0击败关岛，创造队史最大比分赢球纪录，随后，4-0击败
柬埔寨，1-1战平东道主孟加拉国，以小组头名出线，后不敌
吉尔吉斯斯坦，结束了第一次
亚洲洲际赛事之旅。该场赛事中，
巴勒斯坦队内射手
阿塔尔获得了挑战杯金靴。2008年亚足联挑战杯，以色列拒绝巴勒斯坦球员出境导致其失去比赛资格。
2010年南非世界杯预选赛，巴勒斯坦也因为同样的理由被判0-3出局。
2014年，在
亚足联挑战杯决赛中，巴勒斯坦1-0击败
菲律宾夺冠，同时获得了2015
澳大利亚亚洲杯最后一张入场券。2014年7月，在FIFA公布的排名中，巴勒斯坦位列世界第85、亚洲第10。同年9月11日，萨义卜成为球队主帅。
2015年亚洲杯，首次参赛的
巴勒斯坦在小组赛中先后0-4负于
日本、1-5不敌
约旦、0-2不敌
伊拉克，小组垫底出局。因为政治原因，赛时，巴勒斯坦队只勉强把22名球员成功带到澳大利亚。而由于封锁越境，这22名球员也鲜有完整集训的机会。此外，球队的后勤配备也较为简陋，球队的新闻官
英语水平较差，在新闻发布会时难以履行职责，最终由一名
卡塔尔记者临时客串。而在参加2015
亚洲杯的巴勒斯坦阵容中，球队队员多为难民后裔，队长萨利赫出生在
埃及，13号贾卡出生在
斯洛文尼亚，而17号阿莱克西斯则出生在
智利。此时，
巴勒斯坦全队总身价为246万
英镑，队内身价最高的是17号队员阿历克斯·诺拉姆布埃纳，为30万英镑，其次是效力于
约旦联赛的后卫阿卜杜拉提夫·巴哈达利，身价为22英镑，以及效力于斯洛文尼亚联赛的加卡·哈比沙，身价为17万英镑，其余队员身价皆低于10英镑。
2018世界杯亚洲区预选赛40强赛，
巴勒斯坦在主场战平过
阿拉伯联合酋长国和
沙特阿拉伯。最终8场比赛积12分位列小组第三，居沙特、阿联酋之后无缘出线。2018年3月27日，2019年亚洲杯预选赛结束，D组巴勒斯坦提前出线晋级亚洲杯决赛圈。5月5日，
2019年阿联酋亚洲杯抽签仪式在
迪拜举行，巴勒斯坦与
澳大利亚、
叙利亚、约旦同分在B组。2019年阿联酋亚洲杯，巴勒斯坦在小组赛中0-0战平叙利亚、0-3不敌澳大利亚、0-0战平约旦，小组第三无缘出线。
2022年6月，在亚洲杯预选赛中，巴勒斯坦队小组三战全胜，打进10球并全部零封对手，
巴勒斯坦率先锁定小组头名，第三次晋级亚洲杯正赛。8月25日，
国际足球联合会公布FIFA国家队排名，
巴勒斯坦位列
亚洲第15名。
2024年1月15日，卡塔尔亚洲杯小组赛C组首轮，巴勒斯坦队1-4不敌伊朗队，巴勒斯坦首轮积0分，因净胜球劣势小组排名垫底。1月19日，在小组赛第2轮中，巴勒斯坦队1-1战平
阿联酋国家男子足球队，塔梅尔·赛亚姆比赛中射失点球，阿联酋队的阿贝勒阿齐兹打进乌龙。1月23日，
亚洲杯小组赛C组末轮比赛中，乌代·达巴格打进2球，帮助巴勒斯坦队3-0战胜中国香港队，取得队史亚洲杯首胜。最终巴勒斯坦队小组赛1胜1平1负积4分排名第三，首次在亚洲杯小组赛突围，进入淘汰赛。
2024年1月30日，2023
卡塔尔亚洲杯1/8决赛展开角逐，
巴勒斯坦队1-2不敌东道主卡塔尔队，最终无缘八强。6月7日，在
国际足联世界杯预选赛亚洲区36强阶段5轮中，巴勒斯坦0-0战平
黎巴嫩后，积8分，力压黎巴嫩的3分，锁定小组第二晋级。6月27日，2026世界杯预选赛亚洲区18强赛分组抽签结果出炉，巴勒斯坦队与
韩国、
伊拉克、
约旦、
阿曼、
科威特国家足球队被分到B组。