Where Azure DevOps Services Enviromnent come into play? I am trying to understand where you actually use the environments you setup in a project. I though I could use them to deploy on specific servers from deployment agent which are hosted on another on premise server.

The example given in the documentation shows that you can define the environment inside a deployment job.
But I can't find it inside the UI when defining a release pipeline

Where do you use environments if you're not using a yaml pipeline ?

- stage: deploy
  jobs:
  - deployment: DeployWeb
    displayName: deploy Web App
    pool:
      vmImage: 'Ubuntu-16.04'
    # creates an environment if it doesn't exist
    environment: 'smarthotel-dev'
    strategy:
      runOnce:
        deploy:
          steps:
          - script: echo Hello world
You need to enable the multi-stage pipelines preview feature. Here is a guide to enable preview features.