Lorsque le doge Dandolo proposa aux barons chrétiens de renverser l'usurpateur byzantin, un grand tumulte éclata: ce projet contrariait leur impatience; mais les Vénitiens exposèrent habilement qu'il était nécessaire de laisser des alliés à Constantinople avant d'envahir la Syrie, et que, sans cette expédition, ils se verraient éternellement réduits à manquer d'argent et de vivres, et se dévoueraient à une perte certaine. Jacques d'Avesnes, Simon de Montfort, Gui de Coucy, Pierre d'Amiens, répliquaient avec enthousiasme qu'ils n'avaient pas quitté leurs foyers pour combattre un tyran, mais pour délivrer le tombeau et la croix de Jésus-Christ. Le légat du pape demandait également qu'on se dirigeât vers Jérusalem. Au milieu de ces discussions parut le fils d'Isaac Comnène, qui venait implorer la générosité des barons franks: il promettait de fournir aux croisés, s'ils le plaçaient sur le trône de Byzance, des vivres pour un an et un secours de dix mille hommes: il ajoutait que leur expédition à Constantinople ne retarderait que d'un mois leur arrivée en Palestine. L'abbé de Looz fut ébranlé par ses prières, et engagea les barons chrétiens à ne point se séparer. Le comte de Flandre, le marquis de Montferrat, Quènes de Béthune, Miles de Brabant, Renier de Trith, Anselme de Kayeu émirent le même avis, et leur opinion triompha.
Cependant la flotte flamande de la comtesse Marie, après avoir reconnu aux bords du Tage les colonies que d'autres pèlerins, venus des mêmes lieux, y avaient fondées, s'était arrêtée sur les rivages de l'Afrique pour y conquérir une ville remise depuis aux chevaliers de Saint-Jacques de l'Epée, et elle avait poursuivi sa route en saluant les murailles d'Almeria et de Carthagène. Les chevaliers croisés admirèrent de loin, non sans quelque secret sentiment de douleur et de regret, la belle plaine de Valence cultivée par les Mores; mais bientôt ils se consolèrent en apercevant la tour de Peniscola qui formait la limite des pays occupés par les infidèles. Arrivés aux bouches de l'Ebre, ils laissèrent derrière eux d'un côté Tarragone, Barcelone et Leucate, de l'autre les îles Baléares, qui payaient chaque année au roi d'Aragon un tribut d'étoffes de soie. Enfin ils passèrent devant Narbonne et atteignirent le port de Marseille qu'entouraient, au sein d'un amphithéâtre de montagnes, la cité épiscopale et la magnifique abbaye de Saint Victor. C'était à Marseille que les croisés devaient recevoir des nouvelles de l'expédition qui s'était rendue à Venise. Ils apprirent avec étonnement que, malgré les menaces d'Innocent III, l'avarice des Vénitiens retenait l'élite des chevaliers d'Occident au siége de Zara, et le seul message qui leur parvint leur porta l'ordre de mettre à la voile dans les derniers jours de mars en se dirigeant vers le promontoire de Méthone.
Depuis deux mois, la flotte flamande avait jeté l'ancre dans les eaux profondes du golfe de Messénie, dominées par les bois d'oliviers de Coron et les ruines de Muszun ou Modon, l'antique Méthone, récemment détruite par Roger de Sicile, petit-fils de Robert Wiscard. La comtesse de Flandre, ne voyant point les Vénitiens quitter l'Adriatique, ordonna au pilote de tourner la proue vers la Syrie. Déjà avaient disparu à l'horizon les cimes du Taygète et du mont Ithome; deux navires étaient seuls restés un peu en arrière quand, en dépassant le cap Malée, ils furent atteints par les premières galères de la flotte vénitienne qui se dirigeait vers la Propontide. Un seul sergent se jeta dans une barque pour rejoindre Baudouin et Dandolo: «Il me samble bien, avait-il dit à ses compagnons, k'ils doient conquerre terre.»
Une terreur profonde régnait à Constantinople: depuis longtemps, on y racontait que Venise équipait une flotte immense pour les guerriers du Nord, qui, couverts de fer et aussi hauts que leurs lances, obéissaient à des chefs plus vaillants que le dieu Mars. L'historien grec Nicétas répète, en l'appliquant aux guerriers franks, ce que les anciens disaient des Gaulois, qu'ils ne craignaient rien si ce n'est la chute du ciel. Il les compare tantôt à des statues d'airain, tantôt à des anges exterminateurs dont les regards seuls donnent la mort. Dès qu'ils eurent abordé dans le Bosphore, au bourg de Saint-Etienne, le tyran Alexis se hâta de leur envoyer des ambassadeurs chargés de présents; mais Quènes de Béthune leur répondit, au nom des barons chrétiens, qu'il cessât de parlementer et commençât par obéir.
Les pèlerins s'étaient divisés en six corps principaux. L'avant-garde avait été confiée au comte de Flandre, parce qu'aucun autre prince n'avait près de lui autant de chevaliers, d'archers et d'arbalétriers. Le second corps obéissait à Henri, frère de Baudouin. Le comte de Saint-Pol, Pierre d'Amiens, Eustache de Canteleu, dirigeaient le troisième. Les autres bataillons comptaient pour chefs le comte de Blois, Matthieu de Montmorency et le marquis de Montferrat. Le 6 juillet, toute l'armée s'assembla dans la plaine de Scutari et traversa le Bosphore. Jacques d'Avesnes combattait au premier rang: un coup de lance l'atteignit au visage, et il eût péri sans le secours de Nicolas de Genlis. Selon une ancienne tradition conservée à Biervliet, ce furent des croisés venus de cette ville qui pénétrèrent les premiers dans la tour de Galata et qui ennoblirent ainsi l'écusson de leur modeste patrie, où ils placèrent l'orgueilleuse devise des tyrans de Constantinople: Βασιλεος βασιλεων, βασιλευων βασιλεοντας. «Je suis le roi des rois, celui qui règne sur ceux qui règnent.»
Pendant ce combat, les vaisseaux de Venise et quelques vaisseaux flamands, qui avaient rejoint Baudouin au siége de Zara, ouvraient leurs voiles à un vent favorable, et se dirigeaient vers le port dont une forte chaîne fermait l'entrée. Une galère flamande, commandée par Gui de Baenst et équipée à Termonde, et un navire italien qu'on nommait l'Aigle, la frappèrent en même temps et la brisèrent. Les deux flottes s'avançaient triomphantes et luttaient de courage. «Alors, dit Marino Sanudo, se forma entre les deux peuples cette amitié célèbre dont l'heureuse mémoire passa aux générations suivantes.»
De toutes parts, les croisés se préparent à l'assaut. Tandis que les Lombards et les Bourguignons gardaient le camp, les Flamands et les Champenois, plus redoutables par leur valeur que par leur nombre, dressaient leurs échelles contre les murailles; mais les mercenaires étrangers dans lesquels se confiait Alexis repoussèrent toutes leurs tentatives. Là périt Pierre de Bailleul.
A la même heure, d'autres croisés attaquèrent Byzance du côté du port. Ils avaient tendu au-dessus de leurs navires de larges peaux de bœufs pour se mettre à l'abri du feu grégeois, et leurs machines de guerre lançaient des pierres énormes au milieu des assiégés. Dandolo, aveugle et âgé de quatre-vingt-quinze ans, s'était fait porter au milieu des combattants: son généreux dévouement décida la victoire. Le tyran Alexis chercha son salut dans la fuite. Le vieil Isaac fut délivré, et son fils entra solennellement dans la cité impériale, placé entre le comte de Flandre et le doge de Venise.
Des hérauts d'armes se rendirent aussitôt en Egypte pour défier les infidèles. Cependant on avait résolu d'attendre la fin de l'hiver pour continuer la guerre. Les barons franks oubliaient la jalousie des Vénitiens et la perfidie des Grecs au milieu des richesses et des plaisirs que leur offrait Byzance; on dit même qu'un jour les croisés flamands voulurent piller une synagogue qu'ils avaient prise pour une mosquée des Sarrasins; mais la trouvant défendue par des Juifs, ils se vengèrent en y mettant le feu. L'incendie qu'ils avaient allumé se répandit si rapidement que bientôt il devint impossible de l'arrêter; de la ville il s'étendit aux faubourgs jusqu'aux bords de la mer, de telle sorte que des galères s'embrasèrent dans le port: une semaine entière s'écoula avant qu'il eût cessé, et ses ravages furent incalculables.
Alexis, fils d'Isaac, avait enfin obtenu que les croisés quitteraient Constantinople pour établir leurs tentes au delà du golfe de Chrysoceras. Le printemps était arrivé, mais il manquait d'argent pour payer les deux cent mille marcs qu'il avait promis; il n'écoutait d'ailleurs que les conseils des Vénitiens qui l'avaient appelé à Zara pour faire échouer la croisade. L'héritier des Comnène parut dans les premiers jours d'avril au camp de Baudouin, et réclama de nouveaux délais.