Missing HTTP client dependencies for spring-cloud-starter-ribbon

I have a simple Spring Boot application which has a simple REST client, that looks something like this:

@Service
public class MyRestClient {

  private static final String url = "http://localhost:8080/";

  private RestTemplate restTemplate;

  @Autowired
  public MyRestClient(RestTemplate restTemplate) {
    this.restTemplate = restTemplate;
  }

  public String invoke() {
    return restTemplate.getForObject(url, String.class);
  }
}

This works perfectly with Spring Boot.

Now I am trying to add Spring Cloud to the project to have Ribbon Client loadbalancing. I followed the links here:

https://spring.io/guides/gs/client-side-load-balancing/

or this here, which seems to be copy and paste but with more updated dependencies:

http://www.baeldung.com/spring-cloud-rest-client-with-netflix-ribbon

Even without adding any annotations to MyRestClient, the moment I add the following:

<dependency>
<groupId>org.springframework.cloud</groupId>
<artifactId>spring-cloud-starter-ribbon</artifactId>
<version>1.3.4.RELEASE</version>
</dependency>

I get the following exception:

 Caused by: org.springframework.beans.BeanInstantiationException: Failed to instantiate [org.springframework.web.client.RestTemplate]: Factory method 'restTemplate' threw exception; nested exception is java.lang.NoClassDefFoundError: org/apache/http/impl/client/HttpClients
        at org.springframework.beans.factory.support.SimpleInstantiationStrategy.instantiate(SimpleInstantiationStrategy.java:189) ~[spring-beans-4.3.11.RELEASE.jar:4.3.11.RELEASE]
        at org.springframework.beans.factory.support.ConstructorResolver.instantiateUsingFactoryMethod(ConstructorResolver.java:588) ~[spring-beans-4.3.11.RELEASE.jar:4.3.11.RELEASE]
        ... 31 common frames omitted
    Caused by: java.lang.NoClassDefFoundError: org/apache/http/impl/client/HttpClients
        at org.springframework.http.client.HttpComponentsClientHttpRequestFactory.<init>(HttpComponentsClientHttpRequestFactory.java:88) ~[spring-web-4.3.11.RELEASE.jar:4.3.11.RELEASE]
        at sun.reflect.NativeConstructorAccessorImpl.newInstance0(Native Method) ~[na:1.8.0_131]
        at sun.reflect.NativeConstructorAccessorImpl.newInstance(NativeConstructorAccessorImpl.java:62) ~[na:1.8.0_131]
        at sun.reflect.DelegatingConstructorAccessorImpl.newInstance(DelegatingConstructorAccessorImpl.java:45) ~[na:1.8.0_131]
        at java.lang.reflect.Constructor.newInstance(Constructor.java:423) ~[na:1.8.0_131]
        at java.lang.Class.newInstance(Class.java:442) ~[na:1.8.0_131]
        at org.springframework.beans.BeanUtils.instantiate(BeanUtils.java:77) ~[spring-beans-4.3.11.RELEASE.jar:4.3.11.RELEASE]
        at org.springframework.boot.web.client.RestTemplateBuilder.detectRequestFactory(RestTemplateBuilder.java:596) ~[spring-boot-1.5.7.RELEASE.jar:1.5.7.RELEASE]
        at org.springframework.boot.web.client.RestTemplateBuilder.configureRequestFactory(RestTemplateBuilder.java:559) ~[spring-boot-1.5.7.RELEASE.jar:1.5.7.RELEASE]
        at org.springframework.boot.web.client.RestTemplateBuilder.configure(RestTemplateBuilder.java:527) ~[spring-boot-1.5.7.RELEASE.jar:1.5.7.RELEASE]
        at org.springframework.boot.web.client.RestTemplateBuilder.build(RestTemplateBuilder.java:515) ~[spring-boot-1.5.7.RELEASE.jar:1.5.7.RELEASE]
        at org.springframework.boot.web.client.RestTemplateBuilder.build(RestTemplateBuilder.java:501) ~[spring-boot-1.5.7.RELEASE.jar:1.5.7.RELEASE]

Why is my REST client working without this dependency, but then without adding any annotations or anything, the moment I add this dependency, I get this exception?

I tried to add various dependencies from the documentation or examples here and there, like spring-cloud-dependencies (which seem deprecated), spring-cloud-netflix etc. to no avail.

What is the right dependency to add to get this to work?