The AWS::ApiGateway::Deployment needs DependsOn attribute on one AWS::ApiGateway::Method, otherwise CloudFormation will try to create the deployment before the API is ready.
I also faced the same issue. I’m using serverless “function” to create my rest api. As AWS docs says AWS::ApiGateway::Deployment needs DependsOn attribute on one AWS::ApiGateway::Method, therefore I added DependsOn as mentioned below: