Anytime after defeating the Pokemon League, you can battle Tapu Lele, the Island Guardian of Akala, at the end of the Ruins of Life. Like Tapu Koko, it will also be at Level 60. It's ability instantly creates a Psychic Terrain, which boosts its Psychic Type Attacks and prevents priority moves from being used on it.
Thankfully, unlike Tapu Koko, Tapu Lele actually can be paralyzed. This makes it much easier to catch and almost ensures your Pokemon will always move first. After paralyzing Tapu Lele, try to get it's HP as low as possible. Steel Type Pokemon are best against Lele, especially since its moves don't do that much to them. Having False Swipe as an attack on one of your Pokemon also helps, since it will guarantee Tapu Lele is left with at least one HP. If you have the Rotom Power that makes it easier to catch a Wild Pokemon, then you should definitely consider using it here as well.
From there, after getting its HP as low as you think you can, Ultra Balls are the best way to capture it. It will usually take a lot of them to catch this Legendary Pokemon, but they are still your best option. And don't forget to save before battling Tapu Lele, just in case you are going for a certain ability or accidentally knock it out.