Victini- After you defeat Sydney in the Dark Rising HQ, talk to Pete in the next room and he will give it to you.

Heatran- After you find the Gold Ring in Gemstone City's Pokémon Gym. Bring it to the miner
in the Gemstone Mines and he will give you HM Strength. Next, go to Astraeus City and talk to the Black Belt and he will give you the 
HM for Rock Smash, You will need both HMs. Then go to Helios Cavern where you can move the boulders and Heatran will be a the top of the room.

Cresselia- (You might wanna bring flash)After you defeat frontier brain Brandon on Snowflake Route, return to Volton City. The guard will be gone and you can now enter the dark area of Lunar Cave. You can catch Cresselia at the end of the cave.

Latios/Latias- After defeating Brandon (For the first time) you can enter the Endless Garden.  Latios & Latias will be at the end of it. (go north until you see a gap on the right side of the fence and then head right until you can head north again.)

Terrakion- At the top of Vulcan Canyon (Outside).

Cobalion- After you receive HM03 Surf from Gary, go back to Artic Cave and surf upwards on the last floor and he should be easy to find.

Manaphy- (Cut and Surf are Required for this) After you defeat Florina at the Canyon Pathway entrance, return to the Artic Mirage. Zale is now gone and you can enter the building. Once you enter the Sea Labyrinth, Surf to the
Prince's Resort and enter the cave and Arceus Follower Paul will give you Manaphy.

Virizion- In the Forest Cave hidden within Hoia-Baciu.

Arceus- You can catch Arceus in the Sealed Chamber. (Pretty much given to you)

Keldeo- After you defeat Benga in Glacier Cave, you can battle Keldeo.

Dialga/Palkia- In Dimension Castle

Thats all the legendaries I know about, hope this helps!

brickbreaker : Latios and Latias are in the endless garden and I think its either suicune or another similar water legendary is in arctic cave