Era el hijo mayor de Giovanni Dandolo, que era dux de Venecia entre 1280 y 1289. Eso benefició su carrera política, que había empezado en 1274. Asumió varios cargos hasta que, durante el liderazgo de su padre, se convirtió en Duca di Candia (jefe civil y militar) de Creta, que, en esos tiempos, era el centro del imperio colonial de Venecia. Durante todo ese tiempo Andrea Dandolo tuvo sus primeras experiencias militares. En 1291 Andrea Dandolo empezó su carrera militar. En 1292 volvió a ser otra vez Duca di Candia de Creta. Motivado por las incursiones genovesas durante la guerra de Curzola, Andrea Dandolo se volvió en 1296 almirante. Sus éxitos militares contra los genoveses en la Adria y en la costa siciliana como almirante le convirtieron más tarde en Comandante de la Flota Veneciana.
Como Comandante de la Flota Veneciana buscó la batalla decisiva contra los genoveses, que estaban al mando de Lamba Doria, y viceversa. Finalmente ambas flotas se enfrentaron en la batalla de Curzola (8 de septiembre de 1298). Esa batalla resultó ser un desastre para los venecianos. Miles de ellos murieron y miles de ellos fueron hechos prisioneros, entre ellos también Marco Polo, que mandaba una de las noventa y ocho galeras venecianas, el cual, durante su cautiverio en Génova, escribió su libro Il Milione, que iba a cambiar el mundo. Andrea también fue capturado por los genoveses; los Historiadores Contemporáneos informan, de que "Andrea Dandolo, que no podía soportar la vergüenza de la derrota, pegó su cabeza contra la madera del casco de la Galera, y así él se mató a sí mismo", lo que robó a los genoveses la satisfacción de su ejecución.
Aun así los genoveses no pudieron aprovechar su victoria, porque subestimaron la capacidad de recuperación de la República de Venecia y terminaron en empate.
