I have a very nice app Idea, which based on my research it is new, and I am quite sure it would be very much valuable.
At which stage I have to patent it? do I have to patent the idea already, or wait until the app is made?
Typically, one would file a Provisional patent before pursuing a Non-Provisional patent. The requirements for the successful submission of a Provisional Patent are listed on the USPTO.gov website under the Provisional Patent section. These include Technical Specs, Technical Drawings, etc.
First questions are could you patent the idea and then should you (for example, keeping the key parts secret might be an option if the idea is not made public when you sell the app or offer the relevant service).
Assuming the answer to both questions is yes, then the key timing consideration is to make sure that you are careful about what disclosures you make outside of confidentiality agreements. Generally a patent application should be filed before any public disclosure (of any type) is made. This applies as an absolute rule in Europe, but in the US there is a "grace period" meaning you can disclose something and then file your own US patent up to 12 months later, and the disclosure will not destroy novelty of that US patent. Nevertheless, it may still be safer to file before any disclosure is made.
Tactically, an earlier filing date helps guard against other parties who may by coincidence be developing similar solutions, but a later filing date might be advantageous for delaying cash outlays and allowing for complete development of the invention.