横滨足球俱乐部成立于1999年，当时横滨市两大球队：
横滨飞翼和
横滨水手合并后的第二年，一些横滨飞翼的球迷不认为自己应该支持合并后的横滨水手，因为实际上飞翼已经解散，和横滨水手是横滨飞翼的同市死敌。所以，他们向公众募捐，与国际管理集团结盟，和集合横滨飞翼的球迷，成立了横滨Fulie体育俱乐部（Yokohama Fulie Sports Club）。然后他们仿效巴塞罗那采用的社会学模式，在Fulie体育俱乐部下成立了横滨足球俱乐部，这是日本首家由球迷拥有和经营的球队。
成立后的首季（即1999年），横滨足球俱乐部聘请了前
联邦德国国家足球队球星
皮埃尔·利特巴尔斯基为经理，首位在欧洲职业联赛效力的日本球员奥寺康彦担任主席。他们首季只能获准于
日本足球联赛（JFL联赛），未能直接于顶级联赛角逐。球队在日本足球联赛连续夺得两个赛季冠军后升级至
日本职业足球乙级联赛（J2联赛）。
球队在J2联赛角逐了6个赛季，在2001年至2005年位列中游。不过，他们于2006年赢得J2联赛冠军，获得直接升级至
日本职业足球联赛（J1联赛）的资格。在2007年，即俱乐部成立的九年后，他们首次于日本联业足球顶级联赛亮相。
横滨足球俱乐部虽然在2005年只能在12支参加J2联赛球队中排第11，但俱乐部在2006赛季表现出色获得联赛第一升入J1联赛。他们有如戏剧般成功的故事在日本带来很大的震撼，因为横滨足球俱乐部的财政不太健康，连自己的主场馆和会址也没有。每位球员要做他们自己的事，包括清洗球衣和搬龙门架；阵中一些球员曾是
日本国家足球队国脚，如39岁的
三浦知良、37岁的
山口素弘和同样已37岁的
小村德男。球队在赛前热身赛全部落败，即使对手只是大学生。球队在首场联赛落败后选择更换主教练为38岁的
高木琢也，他是一个缺乏经验的新人，并且很多人都不相信他可以带领球队在本赛季取得好的表现。高木琢也着重防守和简单战术，执教的前15场比赛没有失球，最终赢得联赛冠军。
2007赛季，横滨足球俱乐部打破J1联赛多项纪录，包括最快降级、最少入球、最多失球、最少积分等。（这一记录被2014赛季的
德岛漩涡打破）