Let say I have a theme that contains both page.php and index.php.
I also has a Permalink http://www.example.com/.../post-type/post-title/ to a post.
Will WordPress use page.php first, and then use index.php if page.php is not found?
Right now, the URL is leading to index.php, which is not what I expected.
This defined Permalink http://www.example.com/.../post-type/post-title/ is a post. You do not access page.php for this, so use single.php or single-$posttype.php/single-post.php.
See the Page Hierarchy in an image:
A post is not a page, so it will never pass through page.php.
Check out the infographic on WordPress Template Hierarchy in the Codex.
According to this page you'll need a single.php or even a single-{posttype-here}.php.
Wordpress uses what you tell it to use in the "Settings", under one of the sub options (Reading, Writing, etc.). You choose to tell it to use a "static page" for the home page or not. If you choose a static page, then you need to assign a page you create to be the home page, which will use the "page.php" template out of the box if that's the template you assign to the page you just created.
You can then go a step further and create your own page templates based off the original "page.php" template.
Look here for more info: WordPress Codex
