How to convert callback based API into one based on Observable?

I think you need something like this (example given in scala)

import rx.lang.scala.{Observable, Subscriber}

case class Message(message: String)

trait MessageCallback {
  def onMessage(message: Message)
}

object LibraryObject {
  def setCallback(callback: MessageCallback): Unit = {
    ???
  }

  def removeCallback(callback: MessageCallback): Unit = {
    ???
  }

  def start(): Unit = {
    ???
  }
}

def messagesSource: Observable[Message] =
  Observable((subscriber: Subscriber[Message]) ⇒ {
    val callback = new MessageCallback {
      def onMessage(message: Message) {
        subscriber.onNext(message)
      }
    }
    LibraryObject.setCallback(callback)
    subscriber.add {
      LibraryObject.removeCallback(callback)
    }
  })

As for the blocking/non-blocking start(): Usually callback-based architecture separates callback subscription and the process start. In that case, you can create as many messageSources as you want completely independently of when you start() the process. Also the decision whether you fork it or not is completely upon you. Is your architecture different from this?

You should also handle finishing the process somehow. The best would be to add an onCompleted handler to the MessageCallback interface. If you want to handle errors, also add an onError handler. Now behold, you have just declared the fundamental building stone of RxJava, an Observer :-)