diff --git a/clang-tools-extra/clangd/index/remote/Client.cpp b/clang-tools-extra/clangd/index/remote/Client.cpp
--- a/clang-tools-extra/clangd/index/remote/Client.cpp
+++ b/clang-tools-extra/clangd/index/remote/Client.cpp
@@ -91,11 +91,16 @@
     return streamRPC(Request, &remote::SymbolIndex::Stub::Refs, Callback);
   }
 
-  // FIXME(kirillbobyrev): Implement this.
   void
-  relations(const clangd::RelationsRequest &,
-            llvm::function_ref<void(const SymbolID &, const clangd::Symbol &)>)
-      const {}
+  relations(const clangd::RelationsRequest &Request,
+            llvm::function_ref<void(const SymbolID &, const clangd::Symbol &)>
+                Callback) const {
+    streamRPC(Request, &remote::SymbolIndex::Stub::Relations,
+              // Unpack protobuf Relation.
+              [&](std::pair<SymbolID, clangd::Symbol> SubjectAndObject) {
+                Callback(SubjectAndObject.first, SubjectAndObject.second);
+              });
+  }
 
   // IndexClient does not take any space since the data is stored on the
   // server.
diff --git a/clang-tools-extra/clangd/index/remote/Index.proto b/clang-tools-extra/clangd/index/remote/Index.proto
--- a/clang-tools-extra/clangd/index/remote/Index.proto
+++ b/clang-tools-extra/clangd/index/remote/Index.proto
@@ -18,9 +18,13 @@
   rpc FuzzyFind(FuzzyFindRequest) returns (stream FuzzyFindReply) {}
 
   rpc Refs(RefsRequest) returns (stream RefsReply) {}
+
+  rpc Relations(RelationsRequest) returns (stream RelationsReply) {}
 }
 
-message LookupRequest { repeated string ids = 1; }
+message LookupRequest {
+  repeated string ids = 1;
+}
 
 // The response is a stream of symbol messages and the terminating message
 // indicating the end of stream.
@@ -46,7 +50,7 @@
 message FuzzyFindReply {
   oneof kind {
     Symbol stream_result = 1;
-    bool final_result = 2; // HasMore
+    bool final_result = 2;  // HasMore
   }
 }
 
@@ -61,7 +65,7 @@
 message RefsReply {
   oneof kind {
     Ref stream_result = 1;
-    bool final_result = 2; // HasMore
+    bool final_result = 2;  // HasMore
   }
 }
 
@@ -114,3 +118,25 @@
   string header = 1;
   uint32 references = 2;
 }
+
+message RelationsRequest {
+  repeated string subjects = 1;
+  uint32 predicate = 2;
+  uint32 limit = 3;
+}
+
+// The response is a stream of reference messages, and one terminating has_more
+// message.
+message RelationsReply {
+  oneof kind {
+    Relation stream_result = 1;
+    bool final_result = 2;  // HasMore
+  }
+}
+
+// This struct does not mirror clangd::Relation but rather the arguments of
+// SymbolIndex::relations callback.
+message Relation {
+  string subject_id = 1;
+  Symbol object = 2;
+}
diff --git a/clang-tools-extra/clangd/index/remote/marshalling/Marshalling.h b/clang-tools-extra/clangd/index/remote/marshalling/Marshalling.h
--- a/clang-tools-extra/clangd/index/remote/marshalling/Marshalling.h
+++ b/clang-tools-extra/clangd/index/remote/marshalling/Marshalling.h
@@ -38,14 +38,19 @@
   Marshaller() = delete;
   Marshaller(llvm::StringRef RemoteIndexRoot, llvm::StringRef LocalIndexRoot);
 
+  // FIXME(kirillbobyrev): Switch from Optional to Expected.
   llvm::Optional<clangd::Symbol> fromProtobuf(const Symbol &Message);
   llvm::Optional<clangd::Ref> fromProtobuf(const Ref &Message);
+  llvm::Optional<std::pair<clangd::SymbolID, clangd::Symbol>>
+  fromProtobuf(const Relation &Message);
 
   llvm::Expected<clangd::LookupRequest>
   fromProtobuf(const LookupRequest *Message);
   llvm::Expected<clangd::FuzzyFindRequest>
   fromProtobuf(const FuzzyFindRequest *Message);
   llvm::Expected<clangd::RefsRequest> fromProtobuf(const RefsRequest *Message);
+  llvm::Expected<clangd::RelationsRequest>
+  fromProtobuf(const RelationsRequest *Message);
 
   /// toProtobuf() functions serialize native clangd types and strip IndexRoot
   /// from the file paths specific to indexing machine. fromProtobuf() functions
@@ -54,9 +59,12 @@
   LookupRequest toProtobuf(const clangd::LookupRequest &From);
   FuzzyFindRequest toProtobuf(const clangd::FuzzyFindRequest &From);
   RefsRequest toProtobuf(const clangd::RefsRequest &From);
+  RelationsRequest toProtobuf(const clangd::RelationsRequest &From);
 
-  llvm::Optional<Ref> toProtobuf(const clangd::Ref &From);
   llvm::Optional<Symbol> toProtobuf(const clangd::Symbol &From);
+  llvm::Optional<Ref> toProtobuf(const clangd::Ref &From);
+  llvm::Optional<Relation> toProtobuf(const clangd::SymbolID &Subject,
+                                      const clangd::Symbol &Object);
 
   /// Translates \p RelativePath into the absolute path and builds URI for the
   /// user machine. This translation happens on the client side with the
diff --git a/clang-tools-extra/clangd/index/remote/marshalling/Marshalling.cpp b/clang-tools-extra/clangd/index/remote/marshalling/Marshalling.cpp
--- a/clang-tools-extra/clangd/index/remote/marshalling/Marshalling.cpp
+++ b/clang-tools-extra/clangd/index/remote/marshalling/Marshalling.cpp
@@ -10,6 +10,7 @@
 #include "Headers.h"
 #include "Index.pb.h"
 #include "Protocol.h"
+#include "index/Index.h"
 #include "index/Serialization.h"
 #include "index/Symbol.h"
 #include "index/SymbolID.h"
@@ -33,10 +34,10 @@
 
 namespace {
 
-template <typename MessageT>
-llvm::Expected<llvm::DenseSet<SymbolID>> getIDs(MessageT *Message) {
+template <typename IDRange>
+llvm::Expected<llvm::DenseSet<SymbolID>> getIDs(IDRange IDs) {
   llvm::DenseSet<SymbolID> Result;
-  for (const auto &ID : Message->ids()) {
+  for (const auto &ID : IDs) {
     auto SID = SymbolID::fromStr(StringRef(ID));
     if (!SID)
       return SID.takeError();
@@ -69,7 +70,7 @@
 llvm::Expected<clangd::LookupRequest>
 Marshaller::fromProtobuf(const LookupRequest *Message) {
   clangd::LookupRequest Req;
-  auto IDs = getIDs(Message);
+  auto IDs = getIDs(Message->ids());
   if (!IDs)
     return IDs.takeError();
   Req.IDs = std::move(*IDs);
@@ -100,7 +101,7 @@
 llvm::Expected<clangd::RefsRequest>
 Marshaller::fromProtobuf(const RefsRequest *Message) {
   clangd::RefsRequest Req;
-  auto IDs = getIDs(Message);
+  auto IDs = getIDs(Message->ids());
   if (!IDs)
     return IDs.takeError();
   Req.IDs = std::move(*IDs);
@@ -110,6 +111,19 @@
   return Req;
 }
 
+llvm::Expected<clangd::RelationsRequest>
+Marshaller::fromProtobuf(const RelationsRequest *Message) {
+  clangd::RelationsRequest Req;
+  auto IDs = getIDs(Message->subjects());
+  if (!IDs)
+    return IDs.takeError();
+  Req.Subjects = std::move(*IDs);
+  Req.Predicate = static_cast<RelationKind>(Message->predicate());
+  if (Message->limit())
+    Req.Limit = Message->limit();
+  return Req;
+}
+
 llvm::Optional<clangd::Symbol> Marshaller::fromProtobuf(const Symbol &Message) {
   if (!Message.has_info() || !Message.has_canonical_declaration()) {
     elog("Cannot convert Symbol from protobuf (missing info, definition or "
@@ -178,6 +192,24 @@
   return Result;
 }
 
+llvm::Optional<std::pair<clangd::SymbolID, clangd::Symbol>>
+Marshaller::fromProtobuf(const Relation &Message) {
+  auto SubjectID = SymbolID::fromStr(Message.subject_id());
+  if (!SubjectID) {
+    elog("Cannot convert Relation from protobuf (invalid Subject ID): {0}",
+         SubjectID.takeError());
+    return llvm::None;
+  }
+  if (!Message.has_object()) {
+    elog("Cannot convert Relation from protobuf (missing Object): {0}");
+    return llvm::None;
+  }
+  auto Object = fromProtobuf(Message.object());
+  if (!Object)
+    return llvm::None;
+  return std::make_pair(*SubjectID, *Object);
+}
+
 LookupRequest Marshaller::toProtobuf(const clangd::LookupRequest &From) {
   LookupRequest RPCRequest;
   for (const auto &SymbolID : From.IDs)
@@ -216,6 +248,16 @@
   return RPCRequest;
 }
 
+RelationsRequest Marshaller::toProtobuf(const clangd::RelationsRequest &From) {
+  RelationsRequest RPCRequest;
+  for (const auto &ID : From.Subjects)
+    RPCRequest.add_subjects(ID.str());
+  RPCRequest.set_predicate(static_cast<uint32_t>(From.Predicate));
+  if (From.Limit)
+    RPCRequest.set_limit(*From.Limit);
+  return RPCRequest;
+}
+
 llvm::Optional<Symbol> Marshaller::toProtobuf(const clangd::Symbol &From) {
   Symbol Result;
   Result.set_id(From.ID.str());
@@ -274,6 +316,19 @@
   return Result;
 }
 
+llvm::Optional<Relation> Marshaller::toProtobuf(const clangd::SymbolID &Subject,
+                                                const clangd::Symbol &Object) {
+  Relation Result;
+  *Result.mutable_subject_id() = Subject.str();
+  auto SerializedObject = toProtobuf(Object);
+  if (!SerializedObject) {
+    elog("Can not convert Relation to protobuf (invalid symbol): {0}", Object);
+    return llvm::None;
+  }
+  *Result.mutable_object() = *SerializedObject;
+  return Result;
+}
+
 llvm::Optional<std::string>
 Marshaller::relativePathToURI(llvm::StringRef RelativePath) {
   assert(LocalIndexRoot);
diff --git a/clang-tools-extra/clangd/index/remote/server/Server.cpp b/clang-tools-extra/clangd/index/remote/server/Server.cpp
--- a/clang-tools-extra/clangd/index/remote/server/Server.cpp
+++ b/clang-tools-extra/clangd/index/remote/server/Server.cpp
@@ -90,7 +90,7 @@
     }
     unsigned Sent = 0;
     unsigned FailedToSend = 0;
-    Index->lookup(*Req, [&](const auto &Item) {
+    Index->lookup(*Req, [&](const clangd::Symbol &Item) {
       auto SerializedItem = ProtobufMarshaller->toProtobuf(Item);
       if (!SerializedItem) {
         ++FailedToSend;
@@ -121,7 +121,7 @@
     }
     unsigned Sent = 0;
     unsigned FailedToSend = 0;
-    bool HasMore = Index->fuzzyFind(*Req, [&](const auto &Item) {
+    bool HasMore = Index->fuzzyFind(*Req, [&](const clangd::Symbol &Item) {
       auto SerializedItem = ProtobufMarshaller->toProtobuf(Item);
       if (!SerializedItem) {
         ++FailedToSend;
@@ -150,7 +150,7 @@
     }
     unsigned Sent = 0;
     unsigned FailedToSend = 0;
-    bool HasMore = Index->refs(*Req, [&](const auto &Item) {
+    bool HasMore = Index->refs(*Req, [&](const clangd::Ref &Item) {
       auto SerializedItem = ProtobufMarshaller->toProtobuf(Item);
       if (!SerializedItem) {
         ++FailedToSend;
@@ -169,6 +169,38 @@
     return grpc::Status::OK;
   }
 
+  grpc::Status Relations(grpc::ServerContext *Context,
+                         const RelationsRequest *Request,
+                         grpc::ServerWriter<RelationsReply> *Reply) override {
+    trace::Span Tracer(RelationsRequest::descriptor()->name());
+    auto Req = ProtobufMarshaller->fromProtobuf(Request);
+    if (!Req) {
+      elog("Can not parse RelationsRequest from protobuf: {0}",
+           Req.takeError());
+      return grpc::Status::CANCELLED;
+    }
+    unsigned Sent = 0;
+    unsigned FailedToSend = 0;
+    Index->relations(
+        *Req, [&](const SymbolID &Subject, const clangd::Symbol &Object) {
+          auto SerializedItem = ProtobufMarshaller->toProtobuf(Subject, Object);
+          if (!SerializedItem) {
+            ++FailedToSend;
+            return;
+          }
+          RelationsReply NextMessage;
+          *NextMessage.mutable_stream_result() = *SerializedItem;
+          Reply->Write(NextMessage);
+          ++Sent;
+        });
+    RelationsReply LastMessage;
+    LastMessage.set_final_result(true);
+    Reply->Write(LastMessage);
+    SPAN_ATTACH(Tracer, "Sent", Sent);
+    SPAN_ATTACH(Tracer, "Failed to send", FailedToSend);
+    return grpc::Status::OK;
+  }
+
   std::unique_ptr<clangd::SymbolIndex> Index;
   std::unique_ptr<Marshaller> ProtobufMarshaller;
 };
diff --git a/clang-tools-extra/clangd/unittests/remote/MarshallingTests.cpp b/clang-tools-extra/clangd/unittests/remote/MarshallingTests.cpp
--- a/clang-tools-extra/clangd/unittests/remote/MarshallingTests.cpp
+++ b/clang-tools-extra/clangd/unittests/remote/MarshallingTests.cpp
@@ -10,6 +10,7 @@
 #include "TestFS.h"
 #include "index/Index.h"
 #include "index/Ref.h"
+#include "index/Relation.h"
 #include "index/Serialization.h"
 #include "index/Symbol.h"
 #include "index/SymbolID.h"
@@ -88,9 +89,7 @@
 TEST(RemoteMarshallingTest, SymbolSerialization) {
   clangd::Symbol Sym;
 
-  auto ID = SymbolID::fromStr("057557CEBF6E6B2D");
-  ASSERT_TRUE(bool(ID));
-  Sym.ID = *ID;
+  Sym.ID = llvm::cantFail(SymbolID::fromStr("057557CEBF6E6B2D"));
 
   index::SymbolInfo Info;
   Info.Kind = index::SymbolKind::Function;
@@ -342,6 +341,91 @@
   llvm::consumeError(Deserialized.takeError());
 }
 
+TEST(RemoteMarshallingTest, RelationsRequestSerialization) {
+  clangd::RelationsRequest Request;
+  Request.Subjects.insert(
+      llvm::cantFail(SymbolID::fromStr("0000000000000001")));
+  Request.Subjects.insert(
+      llvm::cantFail(SymbolID::fromStr("0000000000000002")));
+
+  Request.Limit = 9000;
+  Request.Predicate = RelationKind::BaseOf;
+
+  Marshaller ProtobufMarshaller(testPath("remote/"), testPath("local/"));
+
+  auto Serialized = ProtobufMarshaller.toProtobuf(Request);
+  EXPECT_EQ(static_cast<unsigned>(Serialized.subjects_size()),
+            Request.Subjects.size());
+  EXPECT_EQ(Serialized.limit(), Request.Limit);
+  EXPECT_EQ(static_cast<RelationKind>(Serialized.predicate()),
+            Request.Predicate);
+  auto Deserialized = ProtobufMarshaller.fromProtobuf(&Serialized);
+  ASSERT_TRUE(bool(Deserialized));
+  EXPECT_EQ(Deserialized->Subjects, Request.Subjects);
+  ASSERT_TRUE(Deserialized->Limit);
+  EXPECT_EQ(*Deserialized->Limit, Request.Limit);
+  EXPECT_EQ(Deserialized->Predicate, Request.Predicate);
+}
+
+TEST(RemoteMarshallingTest, RelationsRequestFailingSerialization) {
+  clangd::RelationsRequest Request;
+  Request.Subjects.insert(
+      llvm::cantFail(SymbolID::fromStr("0000000000000001")));
+  Request.Subjects.insert(
+      llvm::cantFail(SymbolID::fromStr("0000000000000002")));
+
+  Request.Limit = 9000;
+  Request.Predicate = RelationKind::BaseOf;
+
+  Marshaller ProtobufMarshaller(testPath("remote/"), testPath("local/"));
+
+  auto Serialized = ProtobufMarshaller.toProtobuf(Request);
+  // Not a valid SymbolID.
+  Serialized.add_subjects("ZZZZZZZZZZZZZZZZ");
+  auto Deserialized = ProtobufMarshaller.fromProtobuf(&Serialized);
+  EXPECT_FALSE(Deserialized);
+  llvm::consumeError(Deserialized.takeError());
+}
+
+TEST(RemoteMarshallingTest, RelationsSerializion) {
+  clangd::Symbol Sym;
+  SymbolID ID = llvm::cantFail(SymbolID::fromStr("0000000000000001"));
+  Marshaller ProtobufMarshaller(testPath("remote/"), testPath("local/"));
+
+  Sym.ID = llvm::cantFail(SymbolID::fromStr("0000000000000002"));
+
+  index::SymbolInfo Info;
+  Info.Kind = index::SymbolKind::Function;
+  Info.SubKind = index::SymbolSubKind::AccessorGetter;
+  Info.Lang = index::SymbolLanguage::CXX;
+  Info.Properties = static_cast<index::SymbolPropertySet>(
+      index::SymbolProperty::TemplateSpecialization);
+  Sym.SymInfo = Info;
+
+  // Fill in definition and declaration, Symbool will be invalid otherwise.
+  clangd::SymbolLocation Location;
+  Location.Start.setLine(1);
+  Location.Start.setColumn(2);
+  Location.End.setLine(3);
+  Location.End.setColumn(4);
+  llvm::BumpPtrAllocator Arena;
+  llvm::UniqueStringSaver Strings(Arena);
+  Location.FileURI = testPathURI(
+      "remote/llvm-project/llvm/clang-tools-extra/clangd/Protocol.h", Strings);
+  Sym.CanonicalDeclaration = Location;
+
+  auto Serialized = ProtobufMarshaller.toProtobuf(ID, Sym);
+  auto Deserialized = ProtobufMarshaller.fromProtobuf(*Serialized);
+  ASSERT_TRUE(Deserialized);
+  EXPECT_EQ(ID, Deserialized->first);
+  Sym.CanonicalDeclaration.FileURI = testPathURI(
+      "local/llvm-project/llvm/clang-tools-extra/clangd/Protocol.h", Strings);
+  EXPECT_EQ(toYAML(Sym), toYAML(Deserialized->second));
+
+  *Serialized->mutable_subject_id() = "Not A Symbol ID";
+  EXPECT_FALSE(ProtobufMarshaller.fromProtobuf(*Serialized));
+}
+
 TEST(RemoteMarshallingTest, RelativePathToURITranslation) {
   Marshaller ProtobufMarshaller(/*RemoteIndexRoot=*/"",
                                 /*LocalIndexRoot=*/testPath("home/project/"));